Why apples are functions

2012-07-06 pdf

Introduction

When I first started writing Haskell programs, I often felt powerless without subtyping and dynamic dispatch. Coming from an object-oriented background, these seemed like ubiquitous tools to model and structure programs. Eventually, I learned, like many others before me, that closures and objects are of the same nature. While not very idiomatic, it is indeed possible to translate many object hierarchies to closures, and therefore model programs in Haskell in a similar way as you would in OOP languages. This is quite possibly not the best way to model programs in a functional language, but I still found the exercise to be very enlightening and educational. In this post, I will show how class hierarchies can be translated to closures in the context of building a very simple (and arguably quite abstract) game.

An Initial Game Object

When building a game, we often describe the objects that make up the virtual scene as just that, game objects. Suppose that our game has two types of objects, apples and bananas. We also do not want to limit this game to just these two types of objects, as we might decide to add new ones later on. A natural thing to do in the object-oriented paradigm would be to define a base class, say, GameObject, from which other classes, in this case Apple and Banana, would derive. This would allow us to decouple the rest of the game code from the concrete types of game objects, giving us the ability to add new ones later on without having to change client code. For now, let’s start by just rendering game objects:

class GameObject {
public:
    virtual void render () const = 0;
};


class Apple : public GameObject {
public:
    void render () const { cout << "apple" << endl; }
};


class Banana : public GameObject {
public:
    void render () const { cout << "banana" << endl; }
};

In Haskell, one might try to model the objects in this game using algebraic data types (ADTs) as shown below:

data GameObject = Apple | Banana

render Apple = putStrLn "apple"
render Banana = putStrLn "banana"

The benefit of the C++ version over this is the ability to alter the behaviour of the GameObject class by extending it with new types of objects without modifying client code. In other words, the GameObject class satisfies the open/closed principle, which states that classes should be open for extension, but closed for modification. This principle does not directly translate to the representation using ADTs above; we cannot really add an Orange constructor without modifying the existing code because we could expect this code to pattern-match on the values of GameObject. The ADT solution is closed over the types of game objects.

No Data? That must be Functional!

Notice that GameObject, Apple and Banana have no data, only behaviour. They are basically function objects, which allow one to treat functions like first-class citizens in C++. Function objects can be stored and passed around to get different behaviours at runtime. This C++ code is functional in nature, so there should be a way to come up with a Haskell “equivalent”. A game object, so far, is just something that can render itself, so by capturing this very notion we can arrive at the following Haskell alternative:

data GameObject = GameObject { render :: IO () }

apple  = GameObject $ putStrLn "apple"
banana = GameObject $ putStrLn "banana"

With this approach, we can add oranges without modifying existing code:

orange = GameObject $ putStrLn "orange"

The open/closed principle is preserved in this new version of the Haskell implementation versus our original one.

Notice that in the Haskell version of the code, apples and bananas are no longer types, but functions that construct GameObject values. This is a key point that will accompany us throughout the rest of the tutorial.

Identifying Game Objects with Unique IDs

Suppose that we further develop our game and identify game objects by a unique ID. This unique ID is to be included in the object’s rendering. Our C++ implementation could be updated to the following:

class GameObject {
    int _id;

public:
    GameObject (int id) : _id(id) {}

    int id () const { return _id; }

    virtual void render () const = 0;
};


class Apple : public GameObject {
public:
    Apple (int id) : GameObject(id) {}

    void render () const { cout << "apple " << id() << endl; }
};


class Banana : public GameObject {
public:
    Banana (int id) : GameObject(id) {}

    void render () const { cout << "banana " << id() << endl; }
};

How do we translate this into Haskell?

Same Data, Different Behaviour

The ID is common to all game objects. Our old design adapts to the new situation without any major changes; all we need to do is incorporate the new attribute into the GameObject data type:

data GameObject = GameObject
    { goID   :: Int
    , render :: IO () }

apple  goid = GameObject goid $ putStrLn "apple"
banana goid = GameObject goid $ putStrLn "banana"

Adding data common to all game objects is not a problem, we just need to slightly complicate the GameObject data type to reflect the changes. Notice that since apple and banana are functions that build GameObject values, we must supply them with the game object ID that identifies the game object we are building.

Updating Game Objects

A static game is of course not fun or realistic, so let us update game objects on every frame. Let’s suppose that our apples now have a level attribute. This level is also to be included in the rendering of apples. Furthermore, suppose that apples level up on every game tick. Finally, we wish that our bananas remain static. These requirements may not be very realistic, but they illustrate the next problem without adding too much clutter.

The C++ version of the game could be updated to the following:

class GameObject {
    int _id;

public:
    GameObject (int id) : _id(id) {}

    int id () const { return _id; }

    virtual void render () const = 0;

    virtual void update () {} // Do nothing.
};


class Apple : public GameObject {
    int level;

public:
    Apple (int id) : GameObject(id), level(0) {}

    void render () const { cout << "apple, id: " << id()
                                << ", level: "   << level
                                << endl; }

    void update () { level++; }
};


class Banana : public GameObject {
public:
    Banana (int id) : GameObject(id) {}

    void render () const { cout << "banana " << id() << endl; }

    // Default update version inherited from GameObject.
};

How do we reflect the changes in Haskell? One might be tempted to modify the GameObject data type:

data GameObject = GameObject
    { level  :: Int
    , render :: IO ()
    , ... }

But bananas do not have levels, only apples do. We should not push the level attribute all the way to GameObject itself, as that would imply that all game objects have a level.

Perhaps we could try the following instead:

data GameObject = Apple { level :: Int, ... } | Banana { ... }

But this removes the possibility of adding new kinds of GameObjects later on without modifying existing code, as we saw earlier.

The idea in this new iteration of the game is that while a GameObject is still just something that can render, update, and uniquely identify itself, an apple needs to carry around additional state in the form of a level attribute. How can we model this in Haskell without losing the open/closed property of our implementation?

Closures to the Rescue

With the OOP hat on, we could say that an apple is a type of GameObject that has a level, levels up every certain amount of time, and like other game objects, is uniquely identified and can be rendered. How do we describe the apple in a functional way? We could say:

An Apple is a function that takes a game object ID and a level and returns a GameObject identified by the given ID that renders the given level to the output and the update function of which returns a new GameObject that does exactly the same thing but with the given level increased by 1.

Basically, an apple is not a type, but a function that builds values of the GameObject type. The level attribute of the apple is only used internally by the apple, so we can trap it in a closure and forget about it. We can translate the new version of the game to Haskell as follows:

data GameObject = GameObject
    { goID   :: Int
    , render :: IO ()
    , update :: GameObject }

banana :: Int -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana %d\n" goid
    , update = banana goid }

apple :: Int -> Int -> GameObject
apple level goid =
    GameObject
    { goID   = goid
    , render = printf "apple, id: %d, level %d\n" goid level
    , update = apple (level+1) goid }

The key here was to think of apples not as types, but as functions. The apple function takes all of the attributes of the apple, like the level, and builds a GameObject for us. Once we have that GameObject value, we can forget that it is an apple and use its goID, render, and update functions to manipulate it. This is similar to what we have in the OOP version of the game: once the client code builds an Apple object, it can forget it is an Apple and manipulate it through the interface exposed by GameObject. In OOP, we do this with inheritance and dynamic dispatch. In Haskell and functional programming, we do this with functions.

It is useful in functional programming to stop thinking as functions as simply procedures, and to think of them instead as general mechanisms for abstraction and program modelling. Functions are not just code, they are the building blocks of abstraction. In this game example, we use functions to represent particular types of game objects. The only data type we have actually defined is GameObject. Particular game objects, such as apples and bananas, are not subtypes of a more general GameObject type, but values of that type. At this point, the distinction between function and value becomes very blurry, which we expect from functional programming. We can say that “an apple is a function that builds GameObjects”, or we can more naturally say that “apples are GameObjects”. We can interchangeably treat apples as both functions and values. The distinction is not very important in a functional language.

If you are still new to Haskell, the definition of apple might seem troublesome. Aren’t apples (and bananas) infinitely recursive? Recall:

apple :: Int -> Int -> GameObject
apple level goid =
    GameObject
    { ...
    , update = apple (level+1) goid }

The GameObject created by apple has an apple inside it with the original level increased by 1. That other apple, by definition, has another apple inside it with the original level increased by 2, which in turn has another apple that contains another apple… Indeed, we are building an infinite sequence of apples. Remember, however, that Haskell is lazy. Therefore, the recursive apple call is not evaluated until the value of that expression is needed. Laziness allows us to build an infinite game object like apple, just like it allows us to encode the complete fibonacci sequence as an infinite list:

fib = 0 : 1 : zipWith (+) fib (tail fib)

Laziness gives us the power to deal with infinity. The apple function/value is infinitely recursive, but the game won’t hang trying to evaluate that infinite recursion when it only looks at a given value in the sequence.

Towards More Realistic Updates

Up untill now, we can imagine calling the update function on a GameObject on every frame. To make the game more realistic, let’s make update a function of time by passing in the delta with respect to the previous frame. This is a simple tweak that illustrates our next problem: getting the game to react to external input.

Starting with the C++ implementation, suppose we let the update method take a time delta and let apples level up every 5 seconds:

class GameObject {
    int _id;

public:
    GameObject (int id) : _id(id) {}

    int id () const { return _id; }

    virtual void render () const = 0;

    virtual void update (float dt) {} // Do nothing.
};


class Apple : public GameObject {
    int   level;
    float elapsed;

public:
    Apple (int id) : GameObject(id), level(0), elapsed(0) {}

    void render () const { cout << "apple, id: " << id()
                                << ", level: "   << level
                                << endl; }

    void update (float dt) {
        elapsed += dt;
        if (elapsed >= 5.0f) {
            elapsed = elapsed - 5.0f;
            level++;
        }
    }
};


class Banana : public GameObject {
public:
    Banana (int id) : GameObject(id) {}

    void render () const { cout << “banana “ << id() << endl; }

    // Default update version inherited from GameObject.
}

How can we change our Haskell solution with this new behaviour? A game object is still something that can be rendered, updated, and uniquely identified. The definition from last time suits us quite well, except that the update function now takes a time delta, just as in the C++ version:

data GameObject = GameObject
    { goID   :: Int
    , render :: IO ()
    , update :: Float -> GameObject }

The definition of banana only varies slightly. Its update function ignores the given time delta and returns the original object:

banana :: Int -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana %d\n" goid
    , update = const $ banana goid }

Next, we turn turn to apples. In the previous lesson, we saw how the level attribute, which is unique to apples, could simply be made a function argument to apple. We do the same with the elapsed attribute and add that extra logic to get apples leveled up every 5 seconds:

apple :: Int -> Float -> Int -> GameObject
apple level elapsed goid =
    GameObject
    { goID   = goid
    , render = printf "apple, id: %d, level %d\n" goid level
    , update = \dt ->
        let elapsed' = elapsed + dt
        in if elapsed' >= 5.0
            then apple (level+1) (elapsed' - 5.0) goid
            else apple  level     elapsed'        goid }

An apple’s update function now creates not a static, but a dynamic sequence of apples by reacting to time. More generally, we have added the ability to react to external input, and we could make game objects react to any external event, such as user input or a network message.

Note that the Haskell solution is just as extensible as the C++ version, but without the need of subtyping and dynamic dispatch. The full source code follows:

import Text.Printf

data GameObject = GameObject
    { goID   :: Int
    , render :: IO ()
    , update :: Float -> GameObject }

banana :: Int -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana %d\n" goid
    , update = const $ banana goid }

apple :: Int -> Float -> Int -> GameObject
apple level elapsed goid =
    GameObject
    { goID   = goid
    , render = printf "apple, id: %d, level %d\n" goid level
    , update = \dt ->
        let elapsed' = elapsed + dt
        in if elapsed' >= 5.0
            then apple (level+1) (elapsed' - 5.0) goid
            else apple  level     elapsed'        goid }

Reifying Apple

As a final touch, having an actual Apple data makes our code clearer and allows us to write functions that operate on apples as Apples, rather than apples as GameObjects. The Apple data type could be defined as:

data Apple = Apple
    { level    :: Int
    , elapsed :: Float }

The Apple type definition captures all of the data needed to represent an apple. Given this representation, we can make functions that act directly on the Apple data type. A function responsible for updating apples could now be written as:

updateApple :: Apple -> Float -> Apple
updateApple (Apple goid level elapsed) dt =
    let elapsed' = elapsed + dt
    in if elapsed' >= 5.0
        then Apple goid (level+1) (elapsed' - 5.0)
        else Apple goid  level     elapsed'

Finally, we can change the apple builder to act directly on an Apple and make use of the apple updater we just defined:

apple :: Apple -> Int -> GameObject
apple a@(Apple level elapsed) goid =
    GameObject
    { goID   = goid
    , render = printf "apple, id: %d, level %d\n" goid level
    , update = flip apple goid . updateApple a }

Looking at it another way, the apple builder now defines a kind of explicit upcast operation from Apple to GameObject. The full and updated source code follows:

import Text.Printf

data GameObject = GameObject
    { goID   :: Int
    , render :: IO ()
    , update :: Float -> GameObject }

data Apple = Apple
    { level   :: Int
    , elapsed :: Float }

updateApple :: Apple -> Float -> Apple
updateApple (Apple level elapsed) dt =
    let elapsed' = elapsed + dt
    in if elapsed' >= 5.0
        then Apple (level+1) (elapsed' - 5.0)
        else Apple  level     elapsed'

apple :: Apple -> Int -> GameObject
apple a@(Apple level elapsed) goid =
    GameObject
    { goID   = goid
    , render = printf "apple, id: %d, level %d\n" goid level
    , update = flip apple goid . updateApple a }

banana :: Int -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana %d\n" goid
    , update = const $ banana goid }

Lessons Learned

We have seen how to translate object hierarchies to closures in the context of a simple game. The result is, arguably, a very simple object system in Haskell. This is not the most idiomatic way to model Haskell programs (and arguably, OOP is not the best way to model games in C++), but it hopefully shed some light on the relationship between closures and objects. More importantly, we have seen that functions in Haskell are not just code, but the building blocks of abstraction with which we can model complex programs. Whether you are building an object system or not, some of these lessons should still be valuable.